package com.Algorithm.kmp;

import java.util.Arrays;

/**
 * @author MaoLin Wang
 * @date 2019/11/1520:33
 */
public class KMPDemo {
    public static void main(String[] args) {
        String st1="BBC ABCDAB ABCDABCASFDSFVXTJFAWDZSDGTHZSDASFSGFDGDFBFJKLSJASHDJKNASJ HDKASH DKASJHDJ FHDSJFHSDKJF HJSDHFJ SHFJSDHJ UYOQWQWECXGCVNCNVBNDABDE";
        String str2="BN";

        int[]next=kmpNext(str2);
        System.out.println(Arrays.toString(next));

        int index = kmpSearch(st1, str2, next);
        System.out.println(index);
    }

    /**
     *移动位数 = 已匹配的字符数 - 对应的部分匹配值
     * @param str1 原字符串
     * @param str2 子串
     * @param next 匹配值表
     * @return
     */
    public static int kmpSearch(String str1,String str2,int[] next){
        for (int i = 0,j=0 ;i < str1.length(); i++) {

            while (j>0 && str1.charAt(i) != str2.charAt(j)){
                j=next[j-1];//!!!!!!!!!!!!!!!!!!!!!!!!!
            }

            if (str1.charAt(i)==str2.charAt(j)){
                j++;
            }
            if (j==str2.length()){
                return i-j+1;
            }
        }
        return -1;
    }
    /**
     * 获取到一个字符串（子串）的部分匹配值表
     */
    public static  int[] kmpNext(String dest){
        //保存部分匹配值
        int[]next=new int[dest.length()];
        next[0]=0;//如果字符串长度为1,部分匹配值就是0

        for (int i = 1,j=0; i < dest.length(); i++) {

            //二者不相等，需从next[j-1]获取新的j
            //知道发现有dest.charAt[i]==dest.charAt(j)退出
            while (j>0&&dest.charAt(i)!=dest.charAt(j)){
                j=next[j-1];
            }

            //部分匹配值就是+1
            if (dest.charAt(i)==dest.charAt(j)){
                j++;
            }
            next[i]=j;
        }
        return next;
    }


    //
    public static int[] getNext(String ps) {

        char[] p = ps.toCharArray();

        int[] next = new int[p.length];

        next[0] = -1;

        int j = 0;

        int k = -1;

        while (j < p.length - 1) {

            if (k == -1 || p[j] == p[k]) {

                next[++j] = ++k;

            } else {

                k = next[k];

            }

        }

        return next;

    }
}
